//
// Created by lanlu on 2025/8/8.
//
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};


class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeByRec(inorder, 0, inorder.size() - 1,
            postorder, 0, postorder.size() - 1);
    }

    TreeNode * buildTreeByRec(vector<int> &inorder,int inStart, int inEnd,
                                vector<int> &postorder, int postStart, int postEnd)
    {
        // 递归出口
        if (inStart > inEnd || postStart > postEnd)
        {
            return nullptr;
        }

        int rootVal = postorder[postEnd];
        TreeNode *root = new TreeNode(rootVal);

        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal)
        {
            rootIndex++;
        }

        int leftSize = rootIndex - inStart;
        // 注意这里是左闭右闭区间
        // 第一次 [3,4,2,1,5]  [4,3,2,5,1]
        // 第二次 [3,4,2]      [4,3,2]          右 [5] [5]
        root -> left = buildTreeByRec(inorder, inStart, rootIndex - 1,
            postorder, postStart, postStart + leftSize - 1);
        root -> right = buildTreeByRec(inorder, rootIndex + 1, inEnd,
            postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
};